package leetcode.code0076;

public class Solution extends Solution76 {

	@Override
	public String minWindow(String s, String t) {
		int lens = s.length();
		int lent = t.length();
		String ans = "";
		if (lens < lent) {
			return ans;
		}
		char[] cs = s.toCharArray();
		char[] ct = t.toCharArray();
		// 字典
		Integer[] table = new Integer[128];
		// 写入字典
		for (int i = 0; i < lent; i++) {
			table[ct[i]] = table[ct[i]] == null ? 1 : table[ct[i]] + 1;
		}
		int r = 0;
		while (r < lens && lent != 0) {// 找第一个窗口,涵盖所有t
			if (table[cs[r]] != null) {
				if (table[cs[r]] > 0) {
					lent--;
				}
				table[cs[r]]--;
			}
			r++;
		}
		if (lent != 0) {// 没有这样的窗口
			return ans;
		}
		ans = new String(cs, 0, r);// 第一个窗口内的字符串
		int min = ans.length();
		int l = 0;
		while (r <= lens) {
			if (lent == 0) {// 移动左针,缩小窗口,收集答案
				if (table[cs[l]] != null) {
					table[cs[l]]++;// 释放一个字符 ,添加到字典中
					if (table[cs[l]] > 0) {
						lent++;// 缺一个
						if (r - l < min) {
							min = r - l;
							ans = new String(cs, l, min);
						}
					}
				}
				l++;
			} else {// 移动右针,扩大窗口,找到缺少的那个字符
				if (r == lens)
					break;
				if (table[cs[r]] != null) {
					table[cs[r]]--;// 收录一个字符, 从字典中释放一个字符
					if (table[cs[r]] == 0) {
						lent--;// 找到缺的那个了
					}
				}
				r++;
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
	}

}
